package cn.lishiyuan.algorithm.strings;

/**
 * KMP算法
 */
public class KMPMatcher implements Matcher{

    @Override
    public boolean match(CharSequence source, CharSequence word) {
        return find(source,word) != -1;
    }

    @Override
    public int find(CharSequence source, CharSequence word) {
        // codePoints或者chars
        int[] sourceArray = source.chars().toArray();
        int[] wordsArray = word.chars().toArray();

        if (sourceArray.length < wordsArray.length){
            return -1;
        }

        if (wordsArray.length == 0){
            return -1;
        }

        int[] next = failureFunction(wordsArray);

        int index = -1;

        int i = 0;
        int j = 0;

        while (i < sourceArray.length){
            if(sourceArray[i] == wordsArray[j]){
                // 向后匹配看看是否还相同
                i++;
                j++;
            }else if(j > 0){
                // 非第一个字符就失败
                // 坏字符之前的好前缀的末尾index
                int goodPrefixEnd = j - 1;
                // 对齐， j 就是下个字符的位置
                j = next[goodPrefixEnd] + 1;
            }else {
                // 第一个字符就失败则主串向后
                i++;
            }

            // // 已经到最后一位了，找到了，因为必然是从第一个if过来的在j++后必然超出的word的最大index
            if(j == wordsArray.length){
                // abac ac , 这里也就是 i = 4 j=2；因为必然是从j++和i++过来的
                index = i - j;
                break;
            }
        }

        return index;
    }

    private int[] failureFunction(int[] words){
        // next数组 index是好前缀的最后index，值是最长可匹配前缀子串的最后index
        int[] next = new int[words.length];
        next[0] = -1;
        // 上个长度的最长可匹配前缀子串的最后index
        int maxIndex = -1;

        for (int i = 1; i < words.length; i++){
            if (words[i] == words[maxIndex+1]){
                // 当前长度的末尾字符等于上个长度的next的下个字符则直接在其基础上加一
                maxIndex ++;
            }else {
                // 如果不相等，则需要缩小前缀规模查找
                // words[i] != words[maxIndex+1]表示下个字符与该规模的前缀子串不相同，需要进一步缩小
                // maxIndex != -1 表示没有可匹配子串
                while (maxIndex != -1 && words[i] != words[maxIndex+1]){
                    // 此时我们已经确定i-1 到 0 的最长可匹配后缀等于最长可匹配前缀也就是 0 到 maxIndex
                    // 那么我们需要将这个最长可匹配前缀当作好前缀来处理
                    /**
                     * 比如 当前好前缀是 [123457123456]
                     * 我们已经确定 [12345712345]的最长可匹配前缀是[12345]，我们当前的情况是在此前缀上多了一个6
                     * 这就可以将问题转换成好前缀是[123456]的情况，
                     * 而好前缀是[12345]的情况我们是知道的，所以我们将maxIndex变成前一个好前缀的最长可匹配前缀的endIndex
                     */
                    maxIndex= next[maxIndex];
                }

                // 如果找到了则加一
                if(words[i] == words[maxIndex+1]){
                    maxIndex ++;
                }

            }

            next[i] = maxIndex;
        }

        return next;
    }

}
